package JzOffer.jz43;

import java.util.LinkedList;
import java.util.Queue;

class Solution02 {
	public static void main(String[] args){
		
	}
}

class CBTInserter02 {
	private TreeNode root;
	/**
	 * queue只保存不完整节点，即左/右子树至少一个为空的节点
	 */
	private Queue<TreeNode> queue;

	public CBTInserter02(TreeNode root){
		this.root = new TreeNode();
		this.root.val = root.val;
		this.root.left = root.left;
		this.root.right = root.right;

		queue = new LinkedList<>();
		queue.offer(this.root);
		//初始化时将队列准备好，避免每次插入都从根开始遍历
		while(queue.peek() != null && queue.peek().left != null && queue.peek().right != null){
			//优化:左右孩子都存在的节点，在添加新节点时，可以不用遍历该节点，直接从第一个左孩子或右孩子为空的节点开始遍历(即不完整节点)
			TreeNode node = queue.poll();
			//左右孩子入队
			queue.offer(node.left);
			queue.offer(node.right);
		}
	} 

	public int insert(int v){
		TreeNode parent = queue.peek();
		TreeNode newNode = new TreeNode(v);

		//不从根节点开始遍历，从第一个不完整节点开始检查
		if(parent.left == null){
			parent.left = newNode;
		} else {
			parent.right = newNode;
			//父节点出队(完整节点)，左右孩子入队
			queue.poll();
			queue.offer(parent.left);
			queue.offer(parent.right);
		}
		return parent.val;
	}

	public TreeNode get_root(){
		return this.root;
	}
}
